Zapytania

Limit pamięci: 32 MB

Kryptograf Bajtazar pracuje nad złamaniem szyfru ABB (Agencji Bezpieczeństwa Bajtocji). Doszedł już do tego, że przy odszyfrowywaniu wiadomości będzie musiał wielokrotnie odpowiadać na zapytania postaci: "dla danych liczb naturalnych , i , ile jest takich par liczb naturalnych , że:

• ,
• ,
• , gdzie to największy wspólny dzielnik liczb i ".

Zadanie

Napisz program, który:

• wyczyta ze standardowego wejścia listę zapytań, na które musi odpowiedzieć Bajtazar,
• wyznaczy odpowiedzi na te zapytania,
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną dodatnią liczbę całkowitą (), oznaczającą liczbę zapytań Bajtazara. Każdy z kolejnych wierszy zawiera po trzy liczby całkowite , i (), pooddzielane pojedynczymi odstępami. Każda taka trójka reprezentuje jedno zapytanie.

Wyjście

Twój program powinien wypisać na standardowe wyjście wierszy. Wiersz powinien zawierać jedną liczbę całkowitą: odpowiedź na -te zapytanie z wejścia.

Przykład

Dla danych wejściowych:

2
4 5 2
6 4 3

poprawną odpowiedzią jest:

3
2

Pary uzyskane w pierwszym zapytaniu to: , i , a w drugim: i .

Autor zadania: Jakub Radoszewski.